using namespace std;

template <class T>
struct BinaryTreeVertex {
	T data;
	BinaryTreeVertex<T>* LeftSubtree;
	BinaryTreeVertex<T>* RightSubtree;
	BinaryTreeVertex() {
		this->LeftSubtree = NULL;
		this->RightSubtree = NULL;
	}
	BinaryTreeVertex(T x, BinaryTreeVertex<T>* L, BinaryTreeVertex<T>* R) {
		this->data = x;
		this->LeftSubtree = L;
		this->RightSubtree = R;
	}
};
template <class T>
class BinaryTree {
private:
	BinaryTreeVertex<T>* root;
	T EndTag;
protected:
	void CreateBinaryTree(ifstream& in, BinaryTreeVertex<T>*& subtree);
	void Destroy(BinaryTreeVertex<T>* subroot);
	void PreOrder(BinaryTreeVertex<T>* subroot);
	void InOrder(BinaryTreeVertex<T>* subroot);
	void PostOrder(BinaryTreeVertex<T>* subroot);
	int Height(BinaryTreeVertex<T>* subroot);
	int Size(BinaryTreeVertex<T>* subroot);
public:
	BinaryTree();
	BinaryTree(T value);
	~BinaryTree();
	bool IsEmpty();
	int Height();
	int Size();
	void CreatePreOrder(ifstream& in);
	void PreOrder();
	void InOrder();
	void PostOrder();
	BinaryTreeVertex<T>* GetRoot();
};